package com.xinpan.exercise;

import java.util.HashSet;
import java.util.Set;

public class WordSearch {
    public boolean exist(char[][] board, String word) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Set<Integer> visit = new HashSet<Integer>();
        int h = board.length;
        int w = board[0].length;
        
        for(int i = 0; i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                if(board[i][j] == word.charAt(0))
                {
                    visit.add(i * w + j);
                    if(subExist(board, word, 1, i, j, visit))
                        return true;
                    visit.clear();
                }
                    
            }
        }
        return false;
    }
    public boolean subExist(char[][] board, String word, int p, int r, int c, 
                                Set<Integer> visit)
    {
        if(word.length() == p)
            return true;
        
        int h = board.length;
        int w = board[0].length;
        
        char v = word.charAt(p);
        if(r-1 >= 0 && 
            board[r-1][c] == v && 
            !visit.contains(w*(r-1)+c))
        {
            visit.add(w*(r-1)+c);
            if(subExist(board, word, p+1, r-1, c, visit))
                return true;
            visit.remove(w*(r-1)+c);
        }
        
        if(r+1 < h && 
            board[r+1][c] == v && 
            !visit.contains(w*(r+1)+c))
        {
            visit.add(w*(r+1)+c);
            if(subExist(board, word, p+1, r+1, c, visit))
                return true;
            visit.remove(w*(r+1)+c);
        }
        
        if(c-1 >= 0 && 
            board[r][c-1] == v && 
            !visit.contains(w*(r)+c-1))
        {
            visit.add(w*r+c-1);
            if(subExist(board, word, p+1, r, c-1, visit))
                return true;
            visit.remove(w*r+c-1);
        }
        
        if(c+1 < w && 
            board[r][c+1] == v && 
            !visit.contains(w*r+c+1))
        {
            visit.add(w*r+c+1);
            if(subExist(board, word, p+1, r, c+1, visit))
                return true;
            visit.remove(w*r+c+1);
        }
        return false;
    }
}
